#pragma once

class CPrefixSorting
{
public:
	CPrefixSorting(void);
	~CPrefixSorting(void);

public:
	// Calculate cake revert information.
	void Run(int* pCakeArray, int nCakeCnt);

	// Output revert number of cake.
	void Output();

private:
	// Initialize array.
	void Init(int* pCakeArray, int nCakeCnt);

	// Search for current revert upper bound.
	int UpperBound(int nCakeCnt);

	// Search for current revert lower bound.
	int LowerBound(int* pCakeArray, int nCakeCnt);

	// Main sort function.
	void Search(int step);

	// Is sorted.
	bool IsSorted(int* pCakeArray, int nCakeCnt);

	// Revert information.
	void Revert(int nBegin, int nEnd);

private:
	int* m_CakeArray;	// Cake information array.
	int m_nCakeCnt;		// Cake count.
	int m_nMaxSwap;		// Max swap number, default: m_nCakeCnt * 2.
	int* m_SwapArray;	// Swap result array.

	int* m_ReverseCakeArray;		// Current revert cake information array.
	int* m_ReverseCakeArraySwap;	// Current revert cake information swap result array.
	int m_nSearch;				// Current search count.
};
